package top.pro51.guide.chapter1;

/**
 * @ClassName 用栈来求解汉诺塔问题
 * @Description:
 * @Author: WangWenpeng
 * @date: 14:08 2021/1/11
 * @Version 1.0
 */
public class 用栈来求解汉诺塔问题1 {
    public static int hanoiProblem(int num, String left, String mid, String right) {
        if (num < 1) {
            return 0;
        }
        return process(num, left, mid, right, left, right);
    }

    public static int process(int num, String left, String mid, String right, String from, String to) {
        //只有一层需要移动的时候
        if (num == 1) {
            //如果from或to有一个是mid，说明是从右往中，或从左往中，直接移动即可。
            if (from.equals(mid) || to.equals(mid)) {
                System.out.println("Move 1 from " + from + " to " + to);
                return 1;
            } else {
                //否则说明是从左到右，或从右到左，都需要两步，先到中间，再到目的地
                System.out.println("Move 1 from " + from + " to " + mid);
                System.out.println("Move 1 from " + mid + " to " + to);
                return 2;
            }
        }
        //当层数大于1的时候，且有一个是到中间
        if (from.equals(mid) || to.equals(mid)) {
            //如果是从左到中，或者中到左 another就为右，否则就为左，就是说现在参与的是左中，那么剩下的一个是右，同理右中
            String another = (from.equals(left) || to.equals(left)) ? right : left;
            //递归处理n-1层，从当前的from到另一端，即从做到右，或从右到左
            int part1 = process(num - 1, left, mid, right, from, another);
            //将第N层塔从左移到中或从右移到中
            int part2 = 1;
            System.out.println("Move " + num + " from " + from + " to " + to);
            //将1~N-1层塔全部从右移到中,或者从左移动中
            int part3 = process(num - 1, left, mid, right, another, to);
            return part1 + part2 + part3;
        }

        //从左到右或者从右到左  递归处理n-1层
        else {
            //将1~N-1层塔先全部从左移动到右或从右移到左
            int part1 = process(num - 1, left, mid, right, from, to);
            //将第N层塔从左移动到中 或从右移到中
            int part2 = 1;
            System.out.println("Move " + num + " from " + from + " to " + mid);
            //将1~N-1层塔从右移到左 或相反
            int part3 = process(num - 1, left, mid, right, to, from);
            //N层从中移到右
            int part4 = 1;
            System.out.println("Move " + num + " from " + mid + " to " + to);
            //最后将1~N-1层塔全部从左移到右，交给递归过程
            int part5 = process(num - 1, left, mid, right, from, to);
            return part1 + part2 + part3 + part4 + part5;
        }
    }
}
